#include<iostream>
#include<cstdio>
#include<string.h>
#include<string>
using namespace std;
#define MAXSIZE 100
#define SElemType char 
#define QElemType string
SElemType e,c;
QElemType b,s;
typedef struct SqStack
{
    SElemType  *top;
    SElemType *base;
    int stacksize;
}SqStack;
typedef struct 
{
    QElemType *base1;
    int front;
    int rear;
}SqQueue;
SqQueue InitQueue(SqQueue Q)
{
    Q.base1=new QElemType[MAXSIZE];
    Q.front=Q.rear=0;
    return Q;
}
void QueueInsert(SqQueue &Q,QElemType b)
{
    if((Q.rear+1)%MAXSIZE==Q.front)
    return ;
    Q.base1[Q.rear]=b;
    Q.rear=(Q.rear+1)%MAXSIZE;
    return;
}
void QueueDelete(SqQueue &Q)
{
    if(Q.front==Q.rear)
    return;
    Q.front=(Q.front+1)%MAXSIZE;
    return;
}
QElemType GetHead(SqQueue Q)
{
    if(Q.front!=Q.rear)
    return Q.base1[Q.front];
    else
    return Q.base1[Q.rear];
}
int Length(SqQueue Q)
{
    if(Q.rear>Q.front)
    return Q.rear-Q.front;
    else if(Q.front>Q.rear)
    return MAXSIZE-(Q.front-Q.rear);
    else
    return 0;
}
bool Empty1(SqQueue Q)
{
    if(Q.front==Q.rear)
    return 0;
    else
    return 1;
}
SqStack InitStack(SqStack S)
{
    S.base=new SElemType[MAXSIZE];
    S.top=S.base;
    S.stacksize=MAXSIZE;
    return S;
}
void Push(SqStack &S,SElemType a)
{
    if(S.top-S.base==S.stacksize)
    return;
    *S.top=e;
    S.top++;
    return;
}
bool Empty(SqStack S)
{
    if(S.base==S.top)
    return 1;
    else
    return 0;
}
SElemType Pop(SqStack &S,SElemType e)
{
    if(S.top==S.base)
    return '\0';
    S.top--;
    e=*S.top;
    return e;
}
void Clear(SqStack &S)
{
    if(S.top!=S.base)
    {
        Pop(S,e);
    }
    return ;
}
int main()
{
    int a;
    cout<<"请输入数字来执行不同程序"<<'\n';
    cout<<"输入1执行括号匹配问题"<<'\n';
    cout<<"输入2执行舞伴配对问题"<<'\n';
    cout<<"输入3结束程序"<<'\n';
    while(1)
    {   
        cin>>a;
        int flag;
        if(a==1)
        {
            SqStack S;
            cout<<"初始化顺序栈"<<'\n';
            S=InitStack(S);
            cout<<"初始化成功"<<'\n';
            cout<<"检验输入的括号匹配,输入时用'$'符号结束"<<'\n';
            flag=1;
            while(1)
            {
                cin>>c;
                if(c=='(')
                Push(S,c);
                else if(c==')')
                {
                    if(Empty(S))
                    {
                        flag=0;
                    }
                    if(flag==1)
                    Pop(S,e);
                }
                else
                break;
            }
            if(flag==0)
            {
                cout<<"该括号匹配非法"<<'\n';
                continue;
            }
            if(Empty(S))
            {
                cout<<"该括号匹配合法"<<'\n';
            }
            else
            {
                Clear(S);
                cout<<"该括号匹配非法"<<'\n';
            }
        }
        if(a==2)
        {
            int Maxw;
            char sex;
            SqQueue M;
            SqQueue F;
            cout<<"初始化男队列"<<'\n';
            M=InitQueue(M);
            cout<<"初始化女队列"<<'\n';
            F=InitQueue(F);
            cout<<"请输入舞厅最大可以容纳多少对舞伴"<<'\n';
            cin>>Maxw;
            cout<<"请输入舞者性别，用'F'表示女性，'M'表示男性，再输入姓名，输入'O'表示输入结束"<<'\n';
            while(1)
            { 
                if(min(Length(M),Length(F))>=Maxw)
                {
                    cout<<"舞厅已满，等待下一轮舞会"<<'\n';
                }
                cin>>sex;
                if(sex=='F')
                {
                    cin>>s;
                    QueueInsert(F,s);
                }
                if(sex=='M')
                {
                    cin>>s;
                    QueueInsert(M,s);
                }
                if(sex=='O')
                break;
            }
            for(int i=1;Empty1(M)&&Empty1(F);i++)
            {
                printf("第%d对舞会配对的男士是%s,女士是%s\n",i,GetHead(M).c_str(),GetHead(F).c_str());
                QueueDelete(M);
                QueueDelete(F);
            }
            if(Length(M)>Length(F))
            {
                for(int i=1;Empty1(M);i++)
                {
                    printf("第%d位未配对的男士是%s\n",i,GetHead(M).c_str());
                    QueueDelete(M);
                }
            }
            else if(Length(M)<Length(F))
            {
                for(int i=1;Empty1(F);i++)
                {
                    
                    printf("第%d位未配对的女士是%s\n",i,GetHead(F).c_str());
                    QueueDelete(F);
                }
            }
            else
            cout<<"没有未配对的男士和女士"<<'\n';
        }
        if(a==3)
        break;
    }
    system("pause");
    return 0;
}